#include"Sort.h"

void Swap(int& a, int& b)
{
	int t = a;
	a = b;
	b = t;
}
void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
			}
			else
			{
				break;
			}
			end--;
		}
		arr[end + 1] = tmp;
	}
}


void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
				}
				else
				{
					break;
				}
				end -= gap;
			}
			arr[end + gap] = tmp;
		}
	}
}


void SelectSort(int* arr, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int maxi = begin, mini = begin;
		for (int i = begin; i <= end; i++)
		{
			if (arr[i] > arr[maxi]) maxi = i;
			if (arr[i] < arr[mini]) mini = i;
		}
		Swap(arr[begin], arr[mini]);
		if (maxi == begin) maxi = mini;
		Swap(arr[end], arr[maxi]);
		begin++;
		end--;
	}
}

void CountSort(int* arr, int n)
{
	int max = arr[0], min = arr[0];
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > max) max = arr[i];
		if (arr[i] < min) min = arr[i];
	}
	int range = max - min + 1;
	int* count = new int[range] {0};
	for (int i = 0; i < n; i++)
	{
		count[arr[i] - min]++;
	}
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			arr[j++] = i + min;
		}
	}
	delete[] count;
}

void AdjustDown(int* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child++;
		}
		if (arr[parent] < arr[child])
		{
			Swap(arr[parent], arr[child]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	} 
}
void HeapSort(int* arr, int n)
{
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(arr[end], arr[0]);
		AdjustDown(arr, end, 0);
		end--;
	}
}

int getRandom(int* arr, int left, int right)
{
	int r = left + (rand() % (right - left));
	return arr[r];
}
void QuickSort(int* arr, int l, int r)
{
	if (l >= r) return;
	int k = getRandom(arr, l, r);
	int left = l, right = r, cur = l;
	while (cur <= right)
	{
		if (arr[cur] < k)
		{
			Swap(arr[left++], arr[cur++]);
		}
		else if (arr[cur] > k)
		{
			Swap(arr[right--], arr[cur]);
		}
		else cur++;
	}
	QuickSort(arr, l, left - 1);
	QuickSort(arr, right+1, r);
}


int getMid(int* arr, int left, int right)
{
	int mid = left + (right - left) / 2;
	if (arr[left] < arr[mid])
	{
		if (arr[mid] < arr[right]) return mid;
		else if (arr[right] < arr[left]) return left;
		else return right;
	}
	else
	{
		if (arr[mid] > arr[right]) return mid;
		else if (arr[right] > arr[left]) return left;
		else return right;
	}
}

int partSort(int* arr, int left, int right)
{
	int mid = getMid(arr, left, right);
	Swap(arr[mid], arr[left]);
	int k = left;
	int cur = left + 1, prev = left;
	while (cur <= right)
	{
		if (arr[cur] <= arr[k])
		{
			Swap(arr[++prev], arr[cur]);
		}
		cur++;
	}
	Swap(arr[k], arr[prev]);
	return prev;
}

void QuickSortNonR(int* arr, int left, int right)
{
	/*if (left >= right) return;
	int k = partSort(arr, left, right);
	QuickSortNonR(arr, left, k - 1);
	QuickSortNonR(arr, k+1, right);*/
	stack<int> st;
	st.push(right);
	st.push(left);
	while (!st.empty())
	{
		int left = st.top();
		st.pop();
		int right = st.top();
		st.pop();
		int k = partSort(arr, left, right);
		if (k + 1 < right)
		{
			st.push(right);
			st.push(k + 1);
		}
		if (left < k - 1)
		{
			st.push(k - 1);
			st.push(left);
		}
	}
}

void _msort(int* arr, int* tmp, int left, int right)
{
	if (left >= right) return;
	int mid = left + (right - left) / 2;
	_msort(arr, tmp, left, mid);
	_msort(arr, tmp, mid+1, right);
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int k = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[k++] = arr[begin1++];
		}
		else
		{
			tmp[k++] = arr[begin2++];
		}
	}
	while(begin1 <= end1) tmp[k++] = arr[begin1++];
	while (begin2 <= end2) tmp[k++] = arr[begin2++];
	memcpy(arr + left, tmp + left, sizeof(int) * (end2-left+1));
}
void msort(int* arr, int n)
{
	int* tmp = new int[n] {0};
	_msort(arr, tmp, 0, n - 1);
	delete[] tmp;
}


void _msortNonR(int* arr, int *tmp, int n)
{
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + gap * 2 - 1;
			int k = i;
			if (begin2 >= n) break;
			if (end2 >= n) end2 = n - 1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					tmp[k++] = arr[begin1++];
				}
				else
				{
					tmp[k++] = arr[begin2++];
				}
			}
			while(begin1 <= end1) tmp[k++] = arr[begin1++];
			while (begin2 <= end2) tmp[k++] = arr[begin2++];
			memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		gap *= 2;
	}
}
void msortNonR(int* arr, int n)
{
	int* tmp = new int[n] {0};
	_msortNonR(arr, tmp, n);
	delete[] tmp;
}